class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.size = 0
        self.head = None
        self.last = None

    def get(self, index):
        '''
        查找节点
        :param index:
        :return:
        '''
        if index < 0 or index > self.size:
            raise Exception("超出链表节点范围")
        p = self.head
        for i in range(index):
            p = p.next
        return p

    def insert(self, index, element):
        if index < 0 or index > self.size:
            raise Exception('超出链表节点范围')
        node = Node(element)
        if self.size == 0:
            # 空链表插入数据
            self.head = node
            self.last = node
        elif index == 0:
            # 在头部插入数据
            node.next = self.head
            self.head = node
        elif self.size == index:
            # 在尾部插入数据
            self.last.next = node
            self.last = node
        else:
            # 在链表中间插入数据
            # 1 找到前一个节点
            prev_node = self.get(index - 1)
            # 2 找到后一个节点,并将后一个节点放在新节点next上
            node.next = prev_node.next
            # 3 将新节点放在上一个节点next上
            prev_node.next = node
        self.size += 1

    def remove(self, index):
        if index < 0 or index > self.size:
            raise Exception('超出链表节点范围')
        if index == 0:
            # 删除头节点
            remove_node = self.head
            self.head = remove_node.next
        elif index == self.size - 1:
            # 删除最后一个元素
            prev_node = self.get(index - 1)
            remove_node = prev_node.next
            prev_node.next = None
            self.last = prev_node
        else:
            prev_node = self.get(index - 1)
            next_node = prev_node.next.next
            remove_node = prev_node.next
            prev_node.next = next_node
        self.size -= 1
        return remove_node

    def output(self):
        p = self.head
        while p is not None:
            print(p.data)
            p = p.next


if __name__ == '__main__':
    link = LinkedList()
    link.insert(0, 3)
    link.insert(0, 4)
    link.insert(2, 9)
    link.insert(3, 5)
    link.insert(1, 6)
    link.output()
